1. Field
This disclosure generally relates to the field of video data processing. More particularly, the disclosure relates to digital video encoders.
2. General Background
Compression techniques are currently utilized to compress video signals so that the video signals may be more easily transmitted and stored. A video signal typically includes a number of frames, which each have an assortment of pixels arranged in Macroblocks (“MB”). Rather than sending an original MB, current compression technology allows for sending the residuals between the original MB and its prediction along with the associated motion vector(s) (“MV”) that provide offsets to predict and reconstruct the MB at the receiving device. The current compression techniques assume that there is a certain degree of correlation between successive frames in a video signal. Accordingly, for a current MB in a current picture, the motion estimation (“ME”) process conducts a search of a best MV(s) that points to a prediction MB in a reference frame that provides the closest match to the current MB. For a particular MB, sending the residuals between the MB and its best matched MB in the reference frame along with the associated MV, as opposed to the MB itself, minimizes the amount of data that is sent. However, it is very time consuming to search the best MV per MB in a real-time implementation.
Recent developments have led to a video compression standards called H.264 and MPEG-4 Advanced Video Coding (“AVC”). This standard allows for various features that differ from the previous MPEG standards. The ME process is computationally intensive in the H.264|MPEG-4 AVC standard.
As in other video coding standards, ME in H.264|MPEG-4 AVC is block-based. In other words, pixels are arranged in a block format, and all the pixels within a block are assumed to move in the same direction from frame to frame. However, the H.264|MPEG-4 AVC is much more flexible with respect to block sizes and the number of references per block as compared with other standards. For instance, the H.264|MPEG-4 AVC standard supports a number of different partition sizes per MB, e.g., partitions having dimensions of sixteen by sixteen, sixteen by eight, eight by sixteen, and eight by eight, and sub-partitions having dimensions of eight by eight, eight by four, four by eight, and four by four. The H.264|MPEG-4 AVC standard also supports multiple references per MB.
With respect to ME, the H.264|MPEG-4 AVC standard allows each MB partition and sub-macroblock (“sub-MB”) partition to have its own MVs, and each MB partition to have its own reference picture. This flexibility significantly increases the ME performance, but at a cost of ME complexities. For example, to fully explore all the possible MB partitions and sub-MB partitions along with all the available references, ME may have to be performed several times over multiple references for each MB partition and sub-MB partition per MB. The H.264|MPEG-4 AVC standard reference code has implemented three ME processes: (1) full search; (2) Hexagon Search; and (3) Simplified Hexagon Search.
The full search process scans every candidate in the search window in raster or spiral order and finds the MV with the minimum cost per partition. While the full search can find the best result, it does so with the highest computational complexity out of all the ME processes.
Further, the Hexagon Search uses the hybrid and hierarchical motion search strategies, which include four steps with different search patterns: 1) Predictor selection; 2) Unsymmetrical-cross search; 3) Uneven multi-hexagon-grid search; and 4) Extended hexagon based search. The Hexagon Search generally achieves a faster speed than the full search.
The Simplified Hexagon Search further reduces the complexity of the Hexagon Search. There are two differences between Simplified Hexagon Search and Hexagon Search processes. First, the Simplified Hexagon Search uses fixed thresholds for early termination check as opposed to the variable thresholds based on sum of absolute differences (“SAD”) and quantization parameter (“QP”) value utilized in the Hexagon Search. Second, the Simplified Hexagon Search spends more search effort on the sixteen by sixteen partition and sets much looser thresholds for other partitions for early termination check. The Simplified Hexagon Search generally improves search speed over the Hexagon Search.
While the Simplified Hexagon Search is faster than the full scan search and the Hexagon Search, it still does not provide adequate processing time for the ME. As an H.264|MPEG-4 AVC encoder allows multiple MB partitions and sub-MB partitions, and further allows each partition and sub-partition to have a temporary predicted block from one of several previously encoded reference pictures, the H.264|MPEG-4 encoder has to perform ME several times over multiple references for each partition. The current Simplified Hexagon Search is not fast enough to accommodate ME in a real time encoder utilizing digital signal processing (“DSP”).